A typical digital data processing system includes one or more processors that process programs in the form of a series of "tasks". Generally speaking, a task is a unit of processing which is to be performed by one processor. If a digital data processing system includes a plurality of processors, typically processing can be organized so that the processors may perform at least some of the tasks in parallel, thereby increasing the speed with which processing can be performed.
If a digital data processing system includes a plurality of processors, it is desirable to organize task processing so that all of the processors are kept busy processing tasks to the maximal extent possible, to thereby make maximum use of all of the processors in the system. Under some circumstances, processing may constrained so that, before some tasks can be dispatched for processing by a processor, processing of other tasks must be completed. This may occur, for example, if processing proceeds in a plurality of successive iterations, with each iteration comprising a plurality of tasks, and further with the requirement that all of the tasks of each iteration be completed before processing can begin for any of the tasks for the next iteration. In that case, except in the unlikely event that the time required for the tasks divide equally among the processors, some processors will be idle for at least some period of time towards the end of an iteration.
A number of techniques have been used in connection with the constrained processing described in the previous paragraph to attempt to minimize the amount of idle processor time. In one technique, as a program is being compiled, the compiler assigns tasks to the various processors, which they process during each intration. Alternatively, the tasks can be, for example, maintained in a common area of memory that all of the processors can access, and, when a processor becomes free it can access the list and process the next task on the list.
As a further alternative, various algorithms can be employed at the beginning of an iteration to schedule and allocate tasks among processors by attempting to predict the amount of time each task will take, and the tasks distributed among the processors to attempt to equalize the processing time during the iteration. Typically, the prediction algorithms neglect the observation, which is generally reasonably correct, that a task executed during one iteration will take approximately the same time during the next iteration. Further, the predictive task scheduling algorithms can themselves take a considerable amount of time to process, which may inordinately delay processing during the iteration.